package May.砖墙0502;

import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class Solution {

        public int leastBricks(List<List<Integer>> wall) {
            Map<Integer, Integer> map = new HashMap<>();
            //计算前缀和
            int max = 0;
            for (List<Integer> list : wall) {
                int sum = 0;
                int idx = 0;
                Iterator<Integer> iterator = list.iterator();
                //我们遍历砖墙的每一行，对于当前行，我们从左到右地扫描每一块砖，
                //使用一个累加器记录当前砖的右侧边缘到砖墙的左边缘的距离，
                //将除了最右侧的砖块以外的其他砖块的右边缘到砖墙的左边缘的距离加入到哈希表中。
                while (idx < list.size() - 1) {
                    sum += iterator.next();
                    int cnt = map.getOrDefault(sum, 0) + 1;
                    map.put(sum, cnt);
                    max = Math.max(max, cnt);
                    idx++;
                }
            }
            return wall.size() - max;
        }
    }
/*
由于砖墙是一面矩形，所以对于任意一条垂线，其穿过的砖块数量加上从边缘经过的砖块数量之和是一个定值，即砖墙的高度。

因此，问题可以转换成求「垂线穿过的砖块边缘数量的最大值」，用砖墙的高度减去该最大值即为答案。

虽然垂线在每行至多只能通过一个砖块边缘，但是每行的砖块边缘也各不相同，因此我们需要用哈希表统计所有符合要求的砖块边缘的数量。

注意到题目要求垂线不能通过砖墙的两个垂直边缘，所以砖墙两侧的边缘不应当被统计。因此，我们只需要统计每行砖块中除了最右侧的砖块以外的其他砖块的右边缘即可。

具体地，我们遍历砖墙的每一行，对于当前行，我们从左到右地扫描每一块砖，使用一个累加器记录当前砖的右侧边缘到砖墙的左边缘的距离，将除了最右侧的砖块以外的其他砖块的右边缘到砖墙的左边缘的距离加入到哈希表中。最后我们遍历该哈希表，找到出现次数最多的砖块边缘，这就是垂线经过的砖块边缘，而该垂线经过的砖块数量即为砖墙的高度减去该垂线经过的砖块边缘的数量。

*/

